package main

import (
	"fmt"
)

//#link: https://leetcode-cn.com/problems/count-good-meals/
func main() {
	deliciousness := []int{2160, 1936, 3, 29, 27, 5, 2503, 1593, 2, 0, 16, 0, 3860, 28908, 6, 2, 15, 49, 6246, 1946, 23, 105, 7996, 196, 0, 2, 55, 457, 5, 3, 924, 7268, 16, 48, 4, 0, 12, 116, 2628, 1468}
	deliciousness = []int{149, 107, 1, 63, 0, 1, 6867, 1325, 5611, 2581, 39, 89, 46, 18, 12, 20, 22, 234}
	deliciousness = []int{1, 3, 1, 3, 5}
	fmt.Println(countPairs(deliciousness))
}

//暴力解法思路为: 两两进行和计算判断是否为 2的幂
func countPairs(deliciousness []int) (ans int) {
	maxValue := 0
	for _, d := range deliciousness {
		if d > maxValue {
			maxValue = d
		}
	}
	cnt := make(map[int]int)
	for _, val := range deliciousness {
		for i := 1; i <= maxValue*2; i = i << 1 {
			ans += cnt[i-val]
		}
		cnt[val]++
	}

	return ans % (1e9 + 7)
}
